package gold.gold04;

/**
 *
 */
public class S1610生存人数 {
    /**
     * 100, 相比于2只是把二维数组换成了2个1维数组, 不过其实也只是从3ms->2ms。
     * 变化不大, 不必斤斤计较。
     */
    public int maxAliveYear3(int[] birth, int[] death) {
        int[] birthed = new int[101];
        int[] dead = new int[101];
        for(int i = 0; i < birth.length; i++){
            birthed[birth[i] - 1900]++;
            dead[death[i] - 1900]++;
        }
        int[] aliveCount = new int[101];
        aliveCount[0] = birthed[0];
        int maxAlive = aliveCount[0];
        int maxYear = 0;
        for(int i = 1; i < 101; i++){
            aliveCount[i] = aliveCount[i - 1] + birthed[i] - dead[i - 1];
            if(aliveCount[i] > maxAlive){
                maxAlive = aliveCount[i];
                maxYear = i;
            }
        }
        return maxYear + 1900;
    }
    /**
     * 54, 计算一下每年出生的总人数和死亡的总人数, 然后再计算每一年存活的总人数, 这样少一点复杂度。
     * 注意当年死亡的人也算在那一年存活。
     */
    public int maxAliveYear2(int[] birth, int[] death) {
        int[][] liveCount = new int[101][2];
        for(int i = 0; i < birth.length; i++){
            liveCount[birth[i] - 1900][0]++;
            liveCount[death[i] - 1900][1]++;
        }
        int[] aliveCount = new int[101];
        aliveCount[0] = liveCount[0][0];
        int maxAlive = aliveCount[0];
        int maxYear = 0;
        for(int i = 1; i < 101; i++){
            aliveCount[i] = aliveCount[i - 1] + liveCount[i][0] - liveCount[i - 1][1];
            if(aliveCount[i] > maxAlive){
                maxAlive = aliveCount[i];
                maxYear = i;
            }
        }
        return maxYear + 1900;
    }
    /**
     * 40, 计算每一年存活的人数?
     */
    public int maxAliveYear(int[] birth, int[] death) {
        int[] liveCount = new int[101];
        // Arrays.fill(liveCount, 0);
        for(int i = 0; i < birth.length; i++){
            for(int j = birth[i] - 1900; j <= death[i] - 1900; j++){
                liveCount[j] ++;
            }
        }
        int maxLive = 0;
        int maxYear = 1990;
        for(int i = 0; i < liveCount.length; i++){
            if(liveCount[i] > maxLive){
                maxLive = liveCount[i];
                maxYear = i + 1900;
            }
        }
        return maxYear;
    }
}
